عنوان انگلیسی مقاله: An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem

عنوان فارسی مقاله: روش بهینه سازی الگوریتم مورچگان برای مساله فروشنده دوره گرد احتمالی. 

دسته: ریاضی

فرمت فایل ترجمه شده: WORD (قابل ویرایش)

تعداد صفحات فایل ترجمه شده: 11

ترجمه ی سلیس و روان مقاله آماده ی خرید می باشد.

_______________________________________

چکیده ترجمه:

درمساله فروشنده دوره گرد احتمالی هر مشتری بصورت مساوی الاحتمال نیازبه ملاقات دارد. هدف، یافتن مشتری است که دارای کمترین طول مورد انتظار برای ملاقات تمام مشتریان ، با استراتژی ملاقات زیرمجموعه ای تصادفی از مشتریان به ترتیب نمایش آنها در مسیر باشد. 

‏سوال ما این است که در کدام زمینه یک دورقیاسی میتواند بهترین جواب را دهد. 

‏ما این سوال را با تست کردن ارتباط خروجی دو الگوریتم مورچگان نشان میدهیم، سیستم کولونی مورچه ها (ACS) جواب میدهیم، که توسط دوریگو و گامباردلا برای مسئله فروشنده دوره گرد معرفی شد، و نوع دیگر آن سیستم کولونی مورچه های احتمالی که تابع هدف مساله فروشنده دوره گرد احتمالی را کمینه میکند. 

1. معرفی 

‏در یک مساله مسیر یابی مجموعه V را از بین n ‏مشتری در نظر بگیرید. در هر یک از نمونه های مسئله هر مشتری) یک موقعیت معلوم دارد و مقدار احتمال pi نیاز ملاقات میباشد. برای پاسخ به این سوال نیاز به یافتن یک زیرمجموعه تصاذفی S از V. ‏اصلاح میکند، یک مثال خیلی ساده: برای هر زیر مجموعه از مشتریان، هر کدام را به ترتیب نشان داده شده در دور قیاسی ، ملاقات کن و از مشتریانی که عضو زیر مجموعه نیستند صرفنظر کن. استراتژی با توجه به روش گفته شده ( استراتژی صرفنظری نامیده می شود.

‏روش PTSP ( مساله احتمالی فروشنده دوره گرد) در حالتی که مشتریان باید با یک پایه باقاعده (مثلآ روزانه) ملاقات شوند کاربرد دارد، اما تمام مشتریان نیاز به ملاقات همیشگی ندارند، ویا ‏این یک مساله غیر خطی مشکل است( 2 ‏.1)، و توسط جایل در رساله دکترایش معرفی شده است(3‏). 

‏ناممکن است. در این حالت شخص تحویل دهنده باید یک رویه استاندارد را طی کند(یعنی یک ‏دوریا مسیر قیاسی)، و مشتریانی که نیاز به ملاقات ندارند را صرفنظر کند. مسیر استاندارد کمترین ‏طول مسیر مورد انتظار مربوط به حل بهینه PTSP میباشد. ‏روشهای ابتکاری فراوانی برای پیدا کردن حل زیربهینه مساله وجود دارد. 

‏فرا ابتکاری ها از یک معیار همسایگی استفاده میکند که توسط ایکال ( 4 ‏) و گاویولی (5‏) و همچنین لاتر، برتسیماس - جایلیت-اودونی [ 1] و برتسیماسهول [ 6] ارائه شده است. 

‏اینها شامل ساخت مسیری ابتکاری (منحنی پرکردن فضا و سورت کردن شعاعی), ‏مسیر بهبود ابتکاری است. 

‏اغلب روشهای ابتکاری پیشنهاد شد. از روشهای ابتکاری حل TSP ‏برای حل PTSP ‏استفاده می شود.